/*
 * Copyright (c) 2003-2005 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Erik Hallnor
 */

/**
 * @file
 * Definitions of LRU tag store.
 */

#include <string>

#include "base/intmath.hh"
#include "debug/CacheRepl.hh"
#include "mem/cache/tags/cacheset.hh"
#include "mem/cache/tags/lru.hh"
#include "mem/cache/base.hh"
#include "sim/core.hh"

using namespace std;

// create and initialize a LRU/MRU cache structure
LRU::LRU(unsigned _numSets, unsigned _blkSize, unsigned _assoc,
		unsigned _hit_latency)
: numSets(_numSets), blkSize(_blkSize), assoc(_assoc),
	hitLatency(_hit_latency)
{
	// Check parameters
	if (blkSize < 4 || !isPowerOf2(blkSize)) {
		fatal("Block size must be at least 4 and a power of 2");
	}
	if (numSets <= 0 || !isPowerOf2(numSets)) {
		fatal("# of sets must be non-zero and a power of 2");
	}
	if (assoc <= 0) {
		fatal("associativity must be greater than zero");
	}
	if (hitLatency <= 0) {
		fatal("access latency must be greater than zero");
	}

	blkMask = blkSize - 1;
	setShift = floorLog2(blkSize);
	setMask = numSets - 1;
	tagShift = setShift + floorLog2(numSets);
	warmedUp = false;
	/** @todo Make warmup percentage a parameter. */
	warmupBound = numSets * assoc;

	sets = new CacheSet[numSets];
	blks = new BlkType[numSets * assoc];
	// allocate data storage in one big chunk
	numBlocks = numSets * assoc;
	dataBlks = new uint8_t[numBlocks * blkSize];

	unsigned blkIndex = 0;       // index into blks array
	for (unsigned i = 0; i < numSets; ++i) {
		sets[i].assoc = assoc;

		sets[i].blks = new BlkType*[assoc];

		// link in the data blocks
		for (unsigned j = 0; j < assoc; ++j) {
			// locate next cache block
			BlkType *blk = &blks[blkIndex];
			blk->data = &dataBlks[blkSize*blkIndex];
			++blkIndex;

			// invalidate new cache block
			blk->invalidate();

			//EGH Fix Me : do we need to initialize blk?

			// Setting the tag to j is just to prevent long chains in the hash
			// table; won't matter because the block is invalid
			blk->tag = j;
			blk->whenReady = 0;
			blk->isTouched = false;
			blk->size = blkSize;
			sets[i].blks[j]=blk;
			blk->set = i;
		}
	}
}

LRU::~LRU()
{
	delete [] dataBlks;
	delete [] blks;
	delete [] sets;
}

	LRU::BlkType*
LRU::accessBlock(Addr addr, Cycles &lat, int master_id)
{
	Addr tag = extractTag(addr);
	unsigned set = extractSet(addr);
	BlkType *blk = sets[set].findBlk(tag);
	lat = hitLatency;
	if (blk != NULL) {
		// move this block to head of the MRU list
		// Since we are now using RRIP, we do not need to move the block to the head.
		//	sets[set].moveToHead(blk);
		//	DPRINTF(CacheRepl, "set %x: moving blk %x to MRU\n",
		//			set, regenerateBlkAddr(tag, set));
		blk->RRPV = 0;
		if (blk->whenReady > curTick()
				&& cache->ticksToCycles(blk->whenReady - curTick()) > hitLatency) {
			lat = cache->ticksToCycles(blk->whenReady - curTick());
		}
		blk->refCount += 1;
	}

	return blk;
}


LRU::BlkType*
LRU::findBlock(Addr addr) const
{
	Addr tag = extractTag(addr);
	unsigned set = extractSet(addr);
	BlkType *blk = sets[set].findBlk(tag);
	return blk;
}


/*
 * Modified by Taylor Wood
 * Implemented 2-bit SRRIP block replacement policy
 */
	LRU::BlkType*
LRU::findVictim(Addr addr, PacketList &writebacks)
{
	unsigned set = extractSet(addr);
	// grab a replacement candidate
	// Here the 2-bit SRRIP block replacement policy
	// is implemented when finding a victim
	while (true) {
		for (unsigned i = 0; i < assoc; ++i) {
			if (sets[set].blks[i]->RRPV >= 3) {
				if (sets[set].blks[i]->isValid()) {
					DPRINTF(CacheRepl, "set %x: selection blk %x for replacement\n",
						set, regenerateBlkAddr(sets[set].blks[i]->tag, set));
				}
				return sets[set].blks[i];
			}
		}
		// 3 wasn't found, so increment everything
		for (unsigned i = 0; i < assoc; ++i) {
			sets[set].blks[i]->RRPV++;
		}
	}
}

	void
LRU::insertBlock(Addr addr, BlkType *blk, int master_id)
{
	if (!blk->isTouched) {
		tagsInUse++;
		blk->isTouched = true;
		if (!warmedUp && tagsInUse.value() >= warmupBound) {
			warmedUp = true;
			warmupCycle = curTick();
		}
	}

	// If we're replacing a block that was previously valid update
	// stats for it. This can't be done in findBlock() because a
	// found block might not actually be replaced there if the
	// coherence protocol says it can't be.
	if (blk->isValid()) {
		replacements[0]++;
		totalRefs += blk->refCount;
		++sampledRefs;
		blk->refCount = 0;

		// deal with evicted block
		assert(blk->srcMasterId < cache->system->maxMasters());
		occupancies[blk->srcMasterId]--;

		blk->invalidate();
	}

	blk->isTouched = true;
	// Set tag for new block.  Caller is responsible for setting status.
	blk->tag = extractTag(addr);

	// deal with what we are bringing in
	assert(master_id < cache->system->maxMasters());
	occupancies[master_id]++;
	blk->srcMasterId = master_id;
	// Update RRPV
	blk->RRPV = 2;

	unsigned set = extractSet(addr);
	sets[set].moveToHead(blk);
}

	void
LRU::invalidate(BlkType *blk)
{
	assert(blk);
	assert(blk->isValid());
	tagsInUse--;
	assert(blk->srcMasterId < cache->system->maxMasters());
	occupancies[blk->srcMasterId]--;
	blk->srcMasterId = Request::invldMasterId;

	// should be evicted before valid blocks
	unsigned set = blk->set;
	sets[set].moveToTail(blk);
}

	void
LRU::clearLocks()
{
	for (int i = 0; i < numBlocks; i++){
		blks[i].clearLoadLocks();
	}
}

	void
LRU::cleanupRefs()
{
	for (unsigned i = 0; i < numSets*assoc; ++i) {
		if (blks[i].isValid()) {
			totalRefs += blks[i].refCount;
			++sampledRefs;
		}
	}
}
